The invention relates generally to error correction.
Present day storage systems employ a number of different approaches to minimize the number of errors that may occur during a data readback process. In one approach, a storage system rereads the data when uncorrectable errors are detected. Each time the reread operation is performed, the operating conditions are varied slightly, for example, by offsetting the transducer from the center of the track. The reread operations repeat until either the erroneous data are corrected or a predetermined number of reread operations has been performed, at which point the reread process may be terminated in accordance with preset system parameters.
One well-known error correction code that may be used to detect and, if possible, correct the errors which occur in the read data is the Reed-Solomon code. It may be expressed as an (n,k) code where the length of the code word is n symbols and the number of data symbols in the code word is k. The number of redundant symbols corresponds to a check symbol portion r, where r=nxe2x88x92k and the minimum code distance, d, is d=(nxe2x88x92k)+1.
In the prior systems which employ conventional Reed-Solomon decoding techniques during the reread or xe2x80x9cread retrialxe2x80x9d process to correct and detect errors in the read data, the same decoding algorithm that was used to decode the data in the initial read is also used during the read retrial process. That is, during a read retrial, the system performs an error correction decoding algorithm, used to correct t symbol errors, where t=(dxe2x88x921)/2, for each reread operation. If each read contains more than t errors, the correction code is unable to recover the data correctly.
This invention features a read retrial process for rereading and decoding stored code words, the read retrial process converting errors to erasures to enhance error correction capability during decoding.
Generally, in one aspect of the invention, the read retrial process reads at least two copies of a code word, compares corresponding symbols in the read code word copies to determine which corresponding symbols are unequal, and performs a decoding operation to decode one of the copies using symbol locations for the unequal corresponding symbols.
Embodiments of the invention may include one or more of the following features.
The code word read by the process may be an (n,k) Reed-Solomon code word of a minimum code distance d. Such a Reed-Solomon code word is capable of correcting any combination of errors and erasures (i.e., errors with known locations) as long as the sum of the number of erasures and twice the number of errors is less than the minimum distance d of the code word. Thus, the code word copies are processed as having xe2x80x9cerasuresxe2x80x9dxe2x80x94errors at the symbol locations for the unequal corresponding symbolsxe2x80x94by a decoding operation that includes an error-erasure decoding operation. By converting errors to erasures, the error-erasure decoding operation can correct as many as 2t erasures if there are no errors.
The symbol locations may be erasure pointers.
The reads may be consecutive reads.
If the error-erasure decoding operation fails, the other of the read copies may be decoded. If the decoding operations for one or both copies fail, then one or more additional copies may be read and used to produce new erasure pointers.
The read retrial scheme of the invention is quite advantageous in that it tolerates almost twice as many symbol errors as prior read retrial approaches by allowing errors to be processed as erasures by a decoding operation. Thus, the error correction capability of a code word that is read back as part of a read retrial process is increased by increasing the total number of correctable errors from t=(dxe2x88x921)/2 to as many as dxe2x88x921.
Other features and advantages of the invention will be apparent from the following detailed description and from the claims.